LeetCode 50、Pow(x,n)

一、题目描述

实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，x^n ）。

示例 1：

输入：x = 2.00000, n = 10
输出：1024.00000

示例 2：

输入：x = 2.10000, n = 3
输出：9.26100

示例 3：

输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25

提示：

• -100.0 < x < 100.0
• -2^31 <= n <= 2^31-1
• -10^4 <= xn <= 10^4

二、题目解析

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 微信：wzb_3377
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// Pow(x,n)（LeetCode 50）：https://leetcode.cn/problems/powx-n/
class Solution {
    public double myPow(double x, int n) {
        
        // 递归终止条件
        if (n == 0) {

            // 任何数的 0 次方的结果都是 1 ，由于题目要求返回 double 类型，因此返回 1.0
            return 1.0;
        
        // 判断 n 是奇数还是偶数
        // 1、如果是偶数
        } else if ((n & 1) == 0) {
            // 那么只需要先计算出 y = x * x 的结果
            // 然后 y 的次幂就是 n / 2
            return myPow(x * x, n / 2);

        // 2、如果是奇数
        } else {

            // 比如 n = 9 ，那么它就可以被划分为 4 + 4 + 1，即 x^4 * x^4 * x
            // 并且，这个时候还需要判断一下 n 是否为负数

            // 如果是正数
            if( n > 0 ){

                // 直接抽离出一个 x 来，然后和 myPow(x * x, n / 2) 进行相乘
                return x * myPow(x * x, n / 2);

            // 如果是负数
            }else{

                /测试*/
                // int a = -9;
                // int b = a / 2;
                // System.out.println(b); 
                // 输出结果为 -4
                /结束测试*/
                // 比如 n = -9
                // 无论正数还是负数，除 2 是向零取整。
                // 此时 n / 2 = -4
                // (x * x)^-4 = x ^ -8
                // 因此 myPow(x * x, n / 2) 的结果还差一个 x ^ -1 才能还原原来的结果 x ^ -9
                // 由于题目要求返回 double 类型，因此这里使用 1.0
                return myPow(x * x, n / 2) * (1.0 / x) ; 
            }   
        }
    }
}

**2、**C++ 代码

class Solution {
public:
    double myPow(double x, int n) {
        // 递归终止条件
        if (n == 0) {

            // 任何数的 0 次方的结果都是 1 ，由于题目要求返回 double 类型，因此返回 1.0
            return 1.0;
        
        // 判断 n 是奇数还是偶数
        // 1、如果是偶数
        } else if ((n & 1) == 0) {
            // 那么只需要先计算出 y = x * x 的结果
            // 然后 y 的次幂就是 n / 2
            return myPow(x * x, n / 2);

        // 2、如果是奇数
        } else {

            // 比如 n = 9 ，那么它就可以被划分为 4 + 4 + 1，即 x^4 * x^4 * x
            // 并且，这个时候还需要判断一下 n 是否为负数

            // 如果是正数
            if( n > 0 ){

                // 直接抽离出一个 x 来，然后和 myPow(x * x, n / 2) 进行相乘
                return x * myPow(x * x, n / 2);

            // 如果是负数
            }else{
                // 比如 n = -9
                // 无论正数还是负数，除 2 是向零取整。
                // 此时 n / 2 = -4
                // (x * x)^-4 = x ^ -8
                // 因此 myPow(x * x, n / 2) 的结果还差一个 x ^ -1 才能还原原来的结果 x ^ -9
                // 由于题目要求返回 double 类型，因此这里使用 1.0
                return myPow(x * x, n / 2) * (1.0 / x) ; 
            }   
        }
    }
};

3、Python 代码

class Solution:
    def myPow(self, x: float, n: int) -> float:


        # 递归终止条件
        if n == 0 :
            return 1.0    
        elif n == -1 :
            # 任何数的 0 次方的结果都是 1 ，由于题目要求返回 double 类型，因此返回 1.0
            return 1/x
        # 判断 n 是奇数还是偶数
        # 1、如果是偶数
        elif n & 1 == 0 :
            # 那么只需要先计算出 y = x * x 的结果
            # 然后 y 的次幂就是 n / 2
            return self.myPow(x * x, n // 2)

        # 2、如果是奇数
        else :

            # 比如 n = 9 ，那么它就可以被划分为 4 + 4 + 1，即 x^4 * x^4 * x
            # 并且，这个时候还需要判断一下 n 是否为负数

            # 如果是正数
            if n > 0  :

                # 直接抽离出一个 x 来，然后和 myPow(x * x, n / 2) 进行相乘
                return x * self.myPow(x * x, n // 2)

            # 如果是负数
            else :
                # 比如 n = -9
                # Python 比较特殊，正数负数除以 2 取整有区别
                # a = -9
                # b = a // 2
                # print(b) 输出为 -5
                # 此时 n / 2 = -5
                # (x * x)^-5 = x ^ -10
                # 因此 myPow(x * x, n / 2) 的结果还差一个 x ^ 1 才能还原原来的结果 x ^ -9
                # 由于题目要求返回 double 类型，因此这里使用 1.0
                return self.myPow(x * x, n // 2) * x